package com.hardy.leecode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * Author: Hardy
 * Date:   2020/6/28
 * Description:
 **/
public class Que3 {

    public static void main(String[] args) {
        String s = "abcabcbb";
        System.out.println(new Solution().lengthOfLongestSubstring(s));
    }

    static class Solution {
        public int lengthOfLongestSubstring(String s) {
            int i = 0;
            int j = 0;
            int max = 0;
            Set<Character> cache = new HashSet<>();

            while (j < s.length()) {
                char c = s.charAt(j);

                if (cache.contains(c)) {
                    cache.remove(s.charAt(i++));
                } else {
                    cache.add(c);
                    max = Math.max(max, cache.size());
                    j++;
                }
            }
            return max;
        }
    }

    static class Solution1 {
        public int lengthOfLongestSubstring(String s) {
            int i = 0;
            int res = 0;
            Map<Character, Integer> cache = new HashMap<>();

            for (int j = 0; j < s.length(); j++) {
                char c = s.charAt(j);
                if (cache.containsKey(c) && cache.get(c) >= i) i = cache.get(c) + 1;

                cache.put(c, j);
                res = Math.max(res, j - i + 1);
            }
            return res;
        }
    }

    static class Solution2 {
        public int lengthOfLongestSubstring(String s) {
            int l = s.length();
            int res = 0;
            String sub = "";

            for (int j = 0; j < l; j++) {
                int idx = sub.indexOf(s.charAt(j));
                if (idx < 0) sub += s.charAt(j);
                else sub = sub.substring(idx + 1, sub.length()) + s.charAt(j);

                res = Math.max(res, sub.length());
            }

            return res;
        }
    }
}
